package com.structure;

public class Trie {
	private int prefix;
	private int count;
	Trie[] TrieNext = new Trie[26];
	
    public Trie() {
    	prefix = 0;
    	count = 0;
    }
    
    public void insert(String word) {
    	Trie p = this;
    	if(word.length() == 0) return;
    	char[] ch = word.toCharArray();
    	for (int i = 0; i < ch.length; i++) {
    		if(p.TrieNext[ch[i] - 'a'] == null) {
    			p.TrieNext[ch[i] - 'a'] = new Trie();
    		}
    		p = p.TrieNext[ch[i] - 'a'];
    		p.prefix++;
		}
    	p.count++;
    }
    
    public boolean search(String word) {
    	Trie p = this;
    	if(word.length() == 0) return true;
    	char[] ch = word.toCharArray();
    	for (int i = 0; i < ch.length; i++) {
    		if(p.TrieNext[ch[i] - 'a'] == null) {
    			return false;
    		}
    		p = p.TrieNext[ch[i] - 'a'];
		}
    	return p.count > 0;
    }
    
    public boolean startsWith(String prefix) {
    	Trie p = this;
    	if(prefix.length() == 0) return true;
    	char[] ch = prefix.toCharArray();
    	for (int i = 0; i < ch.length; i++) {
    		if(p.TrieNext[ch[i] - 'a'] == null) {
    			return false;
    		}
    		p = p.TrieNext[ch[i] - 'a'];
		}
    	return p.prefix > 0;
    }
}
